package leecode

import "math"

func largestSumOfAverages(nums []int, k int) float64 {
	prefix := make([]float64, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		prefix[i+1] = prefix[i] + float64(nums[i])
	}
	dp := make([][]float64, len(nums)+1) //dp数组 dp[i][j] 对于[0:i+1]的nums , 还需要分成j+1段的情况下的最大值
	for i := range dp {
		dp[i] = make([]float64, k+1)
	}
	for i := 1; i < len(dp); i++ {
		dp[i][1] = prefix[i] / float64(i)
	}
	for j := 2; j <= k; j++ {
		for i := j; i <= len(nums); i++ {
			for x := j - 1; x < i; x++ {
				dp[i][j] = math.Max(dp[i][j], dp[x][j-1]+(prefix[i]-prefix[x])/float64(i-x))
			}
		}
	}
	return dp[len(nums)][k]
}

//1959
